package com.liugui.genericsandcollections;

import java.util.Arrays;

/**
 * @ClassName: InsertSort
 * @Author: liugui
 * @Date: 2020-11-04 15:00
 **/
public class Sort{
    /**
     * 插入排序
     * 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，
     * 从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为 O(n^2)
     */
    private static void insertSort(int[] arr){
        int j;// 已排序列表下标
        int t;// 待排序元素
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i-1]){
                t = arr[i]; // 赋值给待排序元素
                for (j = i-1;j>=0 && arr[j] > t;j--){
                    arr[j+1] = arr[j];// 从后往前遍历已排序列表，逐个和待排序元素比较，如果已排序元素较大，则将它后移
                }
                arr[j+1] = t; // 将待排序元素插入到正确的位置
            }
        }
    }

    /**
     * 冒泡排序
     *
     */
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length -i - 1; j++) {
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] ints = {5, 3, 4, 1, 2};
        bubbleSort(ints);
        System.out.println(Arrays.toString(ints));
    }


}
